import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int ret = in.nextInt();
        while(ret-- > 0){
            int n = in.nextInt();
            int m = in.nextInt();
            System.out.println(minTime(n,m));
        }
    }
    private static int minTime(int n, int m){
        int time = 1;
        int tmp = m;
        if(n <= m)
            return 1;
        while(n > tmp){
            tmp *= m;
            time++;
        }
        if(Math.abs(tmp*m-n) < Math.abs(tmp-n))
            time++;
        if(Math.abs(tmp/m-n) <= Math.abs(tmp-n))
            time--;
        return time;
    }
}